/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package african11;

import java.io.IOException;
import java.util.LinkedList;
import java.util.Queue;
import static chanlib.Chan_IO.*;

/**
 * @author robit
 */
public class BattleField{
    /*
      All neccesary to be defined
      including:
      variable, inner class
    */
    // static int A;
    // static void B();
    // static class C

    /*
       One calculation fits all of the cases.
    */
    static void preReckon(){
        return;
    }

    /*
      calculate the answer
    */
    private static void reckon(int line) {
        int N=Int();
        int R=Int();
        int deg[]=new int[N];
        int adj[][]=new int[N][N];
        boolean visited[]=new boolean[N];
        for(int i=0;i<R;i++){
            int v1=Int(),v2=Int();
            adj[v1][v2]++;
            adj[v2][v1]++;
            deg[v1]++;
            deg[v2]++;
        }
        int oddc=0;
        for(int v=0;v<N;v++){
            if(deg[v]%2==1)oddc++;
        }
        
        int evencomps=0,oddcomps=0;
        Queue<Integer> bfs=new LinkedList<Integer>();
        //StringBuilder rep=new StringBuilder();
        for(int v=0;v<N;v++){
            if(visited[v])continue;
            visited[v]=true;
            bfs.add(v);
            // component type: trivial, odd or even
            int comptype=2;
            int node=0;
            while(!bfs.isEmpty()){
                Integer h=bfs.poll();
                if(h==null)break;
                //rep.append(' ').append(h);
                if(deg[h]==0)comptype=0;
                else if(deg[h]%2!=0)comptype=1;
                node++;
                for(int t=0;t<N;t++){
                    if(visited[t] || adj[h][t]==0)continue;
                    visited[t]=true;
                    bfs.add(t);
                }
            }
            //System.out.println(rep);
            bfs.clear();
            if(comptype==2)evencomps++;
            else if(comptype==1)oddcomps++;
            //rep.delete(0,rep.length());
        }
        // Connect each of all components together
        int conn = evencomps+oddcomps;
        int ans=0;
        if(conn<=1){
            ans=oddc/2;
        }else{
            ans=evencomps+oddc/2;
        }
        
        String output=String.format("Case #%d: %d",line,ans);
        writeln(output, OUTFILE);
        //writeln(String.format("N=%d K=%d\n%s", N, K, ans),ANALFILE);
        //println(output);
    }

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) throws IOException {
        /*
           Pre-computing for all cases
        */

        // Just in case!
        //preReckon();
        //while((char)read()!='P');

        /*
          Input-output
        */
        boolean test=false;
        boolean small=false;
        String prob="B";
        String filename;
        if(test) filename="test";
        else{
            if(small) filename=prob+"-small-practice";
            else filename=prob+"-large-practice";
        }
        try {
            /*
               Init IO,plus determination of input line number
             */
            int lineNums = initFileIO(filename);
            for (int i = 1; i <= lineNums; i++) {
                reckon(i);
            }
        } finally {
            endIO();
        }
    }

}
